package com.tree.leetcode.string;

import java.util.Arrays;

/**
 * @ClassName com.tree.leetcode.string
 * Description: <类功能描述>. <br>
 * <p>
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1:
 *
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 *
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 说明:
 *
 * 所有输入只包含小写字母 a-z 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * </p>
 * @Author tree
 * @Date 2020-03-11 22:50
 * @Version 1.0
 */
public class LongestCommonPrefix_14 {
    public static void main(String[] args) {
        String[]  s1 = new String[]{"flower","flow","flight"};

        String[]  s = new String[]{"flow","flower","flight"};
        System.out.println(longestCommonPrefix(s));
        System.out.println(longestCommonPrefix2(s));
    }

    /**
     * 方法一：水平扫描法
     * 思路
     *
     * 首先，我们将描述一种查找一组字符串的最长公共前缀 LCP(S_1 \ldots S_n)LCP(S
     * 1
     * ​
     *  …S
     * n
     * ​
     *  ) 的简单方法。
     * 我们将会用到这样的结论：
     *
     *
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }

    /**
     * 利用sort排序， 最终只用比较第一个与最后一个字符串
     * @param strs
     * @return
     */
    public static String longestCommonPrefix2(String[] strs) {
        Arrays.sort(strs);
        StringBuilder sb = new StringBuilder();
        int len = strs.length;
        for(int i =0; i<len;i++){
            if(strs[0].charAt(i) == strs[len-1].charAt(i)){
                sb.append(strs[0].charAt(i));
            }else {
                break;
            }

        }
        return sb.toString();
    }


}
